package 简单.二插搜索树的最近公共祖先;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;
//两次遍历
public class Solution1 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_p = getPath(root,p);
        List<TreeNode> path_q = getPath(root,q);
        TreeNode ancestor = null;
        for(int i = 0 ; i < path_p.size()&& i<path_q.size();i++){
            if (path_p.get(i) == path_q.get(i)){
                ancestor = path_p.get(i);
            }
        }
        return ancestor;
    }

    public List<TreeNode> getPath(TreeNode root ,TreeNode target){
        ArrayList<TreeNode> path = new ArrayList<>();
        TreeNode node = root;
        while (root != target){
            path.add(node);
            if(target.val < node.val){
                node = node.left;
            }else {
                node = node.right;
            }
        }
        path.add(node);
        return path;
    }
}
